/*
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.


The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1].
*/


class Solution {
public:
    int trap(int A[], int n) {
        if (!n) return 0;
        vector<int> maxl(n, 0);
        vector<int> maxr(n, 0);
        maxl[0] = A[0]; maxr[n-1] = A[n-1];
        for (int i = 1; i < n; i++) {
            maxl[i] = max(maxl[i-1], A[i]);
            maxr[n-i-1] = max(maxr[n-i], A[n-i-1]);
        }
        int water = 0;
        for (int i = 0; i < n; i++) {
            water += min(maxl[i], maxr[i]) - A[i];
        }
        return water;
    }
};

#if 0
class Solution {
public:
    int trap(int A[], int n) {
        int total = 0;
        vector<int> bars(A, (int *)A+n);
        int end = count_water(bars, total);
        // reverse array to count tail
        if (end < n-1) {
            reverse(bars.begin(), bars.end());
            bars.resize(n-end);
            count_water(bars, total);
        }
        return total;
    }
private:
    int count_water(vector<int> &A, int &total) {
        int start = 0;
        bool trap = false;
        vector<int> tmpbars;
        for (int i = 1; i < A.size(); i++) {
            if (trap == false) {
                if (A[i] >= A[start]) start = i; // increasing sequence
                else { tmpbars.push_back(A[i]); trap = true; } // found container
            } else {
                if (A[i] >= A[start]) {
                    int area = (i-start-1)*A[start];
                    for (auto it = tmpbars.begin(); it != tmpbars.end(); it++) area -= *it;
                    total += area; tmpbars.clear(); trap = false; 
                    start = i;  // potential new container starts here
                } else tmpbars.push_back(A[i]);
            }
        }
        return start;
    }
};
#endif
